package leetcode.problems;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by gmwang on 2018/7/25
 * 相似叶子的结点
 */
public class _0825Left_SimilarTrees {
    /**
     * Given a binary tree, find the leftmost value in the last row of the tree.
     * 考虑一棵二叉树的所有叶子。从左到右顺序，这些叶的值形成叶值序列。
     * Example 1:
     * Input:
     *
     *            3
     *          / \
     *         5   1
     *        /\  /\
     *      6  2 9 8
     *        /\
     *       7 4
     *
     * For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
     *
     * Two binary trees are considered leaf-similar if their leaf value sequence is the same.
     * 如果叶值序列相同，则两棵二叉树被认为是叶相似的。
     * Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
     *
     *
     *
     * Note:
     *
     * Both of the given trees will have between 1 and 100 nodes.
     */
    /**
     * @param root1,root2
     * @return
     */
//    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
//        Queue linkedList1 = new LinkedList<>();
//        Queue linkedList2 = new LinkedList<>();
//        linkedList1 = getNodeValue(root1,linkedList1);
//        linkedList2 = getNodeValue(root2,linkedList2);
//        return (linkedList1.equals(linkedList2));
//    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        Queue linkedList1 = new LinkedList<>();
        linkedList1 = getNodeValue(root1,linkedList1);
        return checkNodeValue(root2,linkedList1);
    }

    public Queue getNodeValue(TreeNode root,Queue sum){
        if(root != null){
            if(root.left != null || root.right != null){
                if(root.left != null){
                    sum = getNodeValue(root.left,sum);
                }
                if(root.right != null){
                    sum = getNodeValue(root.right,sum);
                }
            }else{
                sum.add(root.val);
            }
        }
        return sum;
    }
    public boolean checkNodeValue(TreeNode root,Queue sum){
        boolean flag = true;
        if(root != null){
            if(root.left != null || root.right != null){
                if(root.left != null){
                    flag = checkNodeValue(root.left,sum);
                    if(flag == false) return flag;
                }
                if(root.right != null){
                    flag = checkNodeValue(root.right,sum);
                    if(flag == false) return flag;
                }
            }else{
                if(root.val != (int)sum.poll()){
                    return false;
                }
            }
        }
        return true;
    }
    @Test
    public void test() {
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode1L = new TreeNode(5);
        TreeNode treeNode1R = new TreeNode(1);
        TreeNode treeNode1LL = new TreeNode(6);
        TreeNode treeNode1LR = new TreeNode(2);
        TreeNode treeNode1RL = new TreeNode(9);
        TreeNode treeNode1RR = new TreeNode(8);
        TreeNode treeNode4RL = new TreeNode(7);
        TreeNode treeNode4RR = new TreeNode(4);
        treeNode1.left = treeNode1L;
        treeNode1.right = treeNode1R;
        treeNode1L.left = treeNode1LL;
        treeNode1L.right = treeNode1LR;
        treeNode1R.left = treeNode1RL;
        treeNode1R.right = treeNode1RR;
        treeNode1LR.left = treeNode4RL;
        treeNode1LR.right = treeNode4RR;
//[3,5,1,6,2,9,8,null,null,7,4]
//[3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]

        TreeNode _treeNode1 = new TreeNode(3);
        TreeNode _treeNode1L = new TreeNode(5);
        TreeNode _treeNode1R = new TreeNode(1);
        TreeNode _treeNode1LL = new TreeNode(6 );
        TreeNode _treeNode1LR = new TreeNode(7);
        TreeNode _treeNode2L = new TreeNode(4);
        TreeNode _treeNode2R = new TreeNode(2);
        TreeNode _treeNode4RL = new TreeNode(9);
        TreeNode _treeNode4RR = new TreeNode(8);
        _treeNode1.left = _treeNode1L;
        _treeNode1.right = _treeNode1R;
        _treeNode1L.left = _treeNode1LL;
        _treeNode1L.right = _treeNode1LR;
        _treeNode1R.left = _treeNode2L;
        _treeNode1R.right = _treeNode2R;
        _treeNode2R.left = _treeNode4RL;
        _treeNode2R.right = _treeNode4RR;
        System.out.println(leafSimilar(treeNode1,_treeNode1));
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}
